package algorithm.graph;

import java.util.Stack;
import java.util.Vector;
/**
 * @Description  深度优先遍历，找到的不是最短路径
 * @author bingo
 * @Date 2018/3/13
 */
public class Path {

    /**图的引用*/
    private Graph G;

   /**起始点*/
    private  int s;

    /**记录dfs的过程中节点是否被访问*/
    private boolean[]  visited;

    /**记录路径, from[i]表示查找的路径上i的上一个节点*/
    private int[] from;

    /**构造函数, 寻路算法, 寻找图graph从s点到其他点的路径*/
    public Path(Graph graph, int s) {
        this.G = graph;
        visited = new boolean[graph.n()];
        from = new int[G.n()];
        for(int i=0;i<G.n();i++){
            visited[i]=false;
            from[i] = -1;
        }
        this.s = s;

        dfs(s);
    }
/***图的深度优先遍历*/
    private void dfs(int v) {
        visited[v]=true;
        for(int i:G.adj(v)){
            if(!visited[i]){
                from[i]=v;
                dfs(i);
            }
        }
    }
    /**查询从s点到w点的路径, 存放在vec中**/
           public Vector path(int w){
               Stack<Integer> s = new Stack<Integer>();
            int p=w;
            while(p!=-1){
                s.push(p);
                p=from[p];
            }
            Vector<Integer> vector = new Vector<>();
            while (!s.empty()){
                vector.add(s.pop());
            }
            return  vector;
            }

    /**打印路径*/
    public void showPath(int w){

        Vector vector = this.path(w);

        for(int i=0;i<vector.size();i++){
            System.out.print(vector.elementAt(i));
            if(i==vector.size()-1){
                System.out.print("");
            }
            else{
                System.out.print("->");
            }
        }


    }

    public static void main(String[] args) {

        Graph sparseGraph= new SparseGraph(7,false);
        ReadGraph read = new ReadGraph();
        read.readGraph(sparseGraph,"demo/testG.txt");
        Path path = new Path(sparseGraph,0);
        path.showPath(6);


    }
}
